Random Early Detection, or RED, is one of a class of mechanisms said to enable active queue management. Active queue management attempts to control buffer occupancy in a manner consistent with higher layer protocol dynamics. Motivations for such mechanisms are discussed in RFC-2309 “Recommendations on Queue Management and Congestion Avoidance in the Internet”.
The alternative to active queue management is to simply let the buffer fill until it overflows. This is generally known as tail drop, since it is the latter part (tail) of a burst which is most often discarded. Early Packet Discard (EPD), which triggers discard prior to actual buffer overflow, is an ATM-specific optimization to the tail drop policy described here.
The most striking difference between RED and Tail Drop schemes, is that while the latter tends under congestion to maintain nearly-full buffers, RED attempts to keep buffers relatively empty. This represents a philosophical change, from viewing buffers as warehouses of bits with which to keep outgoing links busy during periods in which the arrival rate is less than the departure rate, to viewing their primary purpose to be burst absorption. This reflects both the nature of traffic on the Internet (a lot of which is bursty, even when aggregated), and an understanding of the way in which higher layer Internet protocols (specifically TCP) perceive and respond to, network capacity.
Positive effects of managing buffer occupancy via RED, include the following.
(1) Delay and delay variation are reduced through a reduction in queuing delay.
(2) Link utilization is increased due to the avoidance of state synchronization in the higher layer protocols controlling the rate at which individual sources transmit.
(3) Discrimination against bursty traffic sources is eliminated.
(4) Discrimination against flows spanning longer distances, is reduced.
RED was initially proposed in a paper by Floyd and Van Jacobson titled “Random Early Detection Gateways for Congestion Avoidance”, in IEEE/ACM Transactions on Networking, V.1 N.4, August 1993, p. 397-413, available at http://www.aciri.org/floyd/papers/early.pdf. The algorithm defined in this paper supported only best-effort service. Cisco Systems also provides for RED.
Extension of RED to support differentiation of loss probability based on whether a flow conformed to its traffic contract, is discussed in Clark and Fang's paper “Explicit Allocation of Best Effort Delivery Service”, available at http://diffserv.lcs.mit.edu/Papers/exp-alloc-ddc-wf.ps. This paper defines what is generally known as “RED with In and Out” (RIO). Nichols and Ibanez examine use of RIO to support an Assured Service.
For the present invention, RIO is extended from 2 markings (“colors”) to three, to accommodate the 3-color marking proposed for the AF PHEs. This is referred to as Weighted RED (WRED). In systems where packets arrive every 2 clock cycles, the floating point calculations required for the WRED algorithm take too much time and are quite difficult to implement. The present invention involves an approximation of WRED using strict integer arithmetic and probability lookups.